//
// Created by francklinson on 2021/7/16 AT 23:42.
//

//你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个m x n 的矩阵表示， 在这个矩阵中：
//
//0 表示障碍，无法触碰
//1表示地面，可以行走
//        比 1 大的数表示有树的单元格，可以行走，数值表示树的高度
//        每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
//
//你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
//
//你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
//
//可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/cut-off-trees-for-golf-event
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <vector>
#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

class Solution {
private:
    vector<pair<int, int>> movements{{1,  0},
                                     {-1, 0},
                                     {0,  1},
                                     {0,  -1}};
public:
    /**
     * 主体框架
     * @param forest
     * @return
     */
    int cutOffTree(vector<vector<int>> &forest) {
        if (forest[0][0] == 0) return -1;
        auto m = forest.size(), n = forest[0].size();
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq; /// 优先队列  按照树的高度排序
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (forest[i][j] > 1) { /// 把所有的树放入有限队列
                    pq.emplace(forest[i][j], i, j);
                }
            }
        }
        /// 每一棵树被砍倒，必须走到队列里下一棵更高的树去 这之间的路径可以BFS
        pair<int, int> currentTree{0, 0}; // 初始树的位置
        int totalSteps = 0;
        while (!pq.empty()) {
            auto nextTree = make_pair(get<1>(pq.top()), get<2>(pq.top())); // 下一棵更高的树
            pq.pop();
            int thisStep = BFS(forest, currentTree, nextTree); // 调用BFS 搜索两棵树之间的最短距离
            if (thisStep == -1) return -1; // 没有路
            else totalSteps += thisStep;
            forest[nextTree.first][nextTree.second] = 1; // 树变成地
            currentTree = move(nextTree);
        }
        return totalSteps;
    }

    /**
     * BFS 函数 搜索两棵树之间的最短路径
     * @param forest
     * @param currentTree
     * @param nextTree
     * @return
     */
    int BFS(vector<vector<int>> &forest, pair<int, int> &currentTree, pair<int, int> &nextTree) {
        if (currentTree == nextTree) return 0;
        auto m = forest.size(), n = forest[0].size();
        vector<vector<bool>> seen(m, vector<bool>(n, false));
        seen[currentTree.first][currentTree.second] = true;
        queue<pair<int, int>> q;
        q.push(currentTree);
        /// 层序遍历找最短路径
        int level = 0;
        while (!q.empty()) {
            ++level;
            auto levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                auto p = q.front();
                q.pop();
                int r = p.first, c = p.second;
                for (int j = 0; j < 4; ++j) {
                    int nr = movements[j].first + r;
                    int nc = movements[j].second + c;
                    if (nr >= 0 and nr < m and nc >= 0 and nc < n and forest[nr][nc] != 0 and !seen[nr][nc]) {
                        q.emplace(nr, nc);
                        seen[nr][nc] = true;
                        if (nr == nextTree.first and nc == nextTree.second)
                            return level;
                    }
                }

            }
        }
        return -1;
    }

};

int main() {
    vector<vector<int>> forest{{1, 2, 3},
                               {0, 0, 0},
                               {7, 6, 5}};
    vector<vector<int>> forest2{{54581641, 64080174, 24346381, 69107959},
                                {86374198, 61363882, 68783324, 79706116},
                                {668150,   92178815, 89819108, 94701471},
                                {83920491, 22724204, 46281641, 47531096},
                                {89078499, 18904913, 25462145, 60813308}};
    Solution solution;
    cout << solution.cutOffTree(forest) << endl;
    cout << solution.cutOffTree(forest2) << endl;
    return 0;
}

